package Algorithm.search;

/**
 * 35. 搜索插入位置 https://leetcode.cn/problems/search-insert-position
 * 题目简述：给定一个严格升序数组，若目标值存在于数组中则返回其索引，否则返回其按顺序插入的位置（插入位置若有元素则后移）
 */
public class SearchInsert {

    /**
     * 思路：正常二分查找找到就返回。若没找到则while循环结束时low在high右边，且low指针左边的元素都是小于target
     * ，high指针右边元素都是大于target，因此low指向的元素也是大于target，故插入位置就是low指针指向的位置
     */
    public int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while(low <= high) {
            int mid = (low + high) / 2;
            if(nums[mid] == target) return mid;
            else if (nums[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        //此时，low一定在high的右边，且low指针左边的元素一定都是小于target的元素，high指针右边一定都是大于target的元素，因此low指针指向的位置恰好是插入位置
        return low;
    }
}
